package com.ycy.leetcode.tree;

import com.google.common.collect.Lists;
import org.junit.Before;
import org.junit.Test;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class BSTCengXu {

  static class TreeNode {
    TreeNode l;
    TreeNode r;
    int val;

    public TreeNode(int val) {
      this.val = val;
    }
  }

  TreeNode root;

  @Before
  public void before() {
   /*
           5
          /\
      200     1000
      /\       /\
    100 300 700 1500
    /
   50
     */
    TreeNode root = new TreeNode(5);
    root.l = new TreeNode(200);
    root.l.l = new TreeNode(100);
    root.l.r = new TreeNode(300);
    root.l.l.l = new TreeNode(50);

    root.r = new TreeNode(1000);
    root.r.l = new TreeNode(700);
    root.r.r = new TreeNode(1500);
    this.root = root;
  }

  //层序遍历所有节点 使用队列的方式
  public List<List<Integer>> leve(TreeNode root) {
    List<List<Integer>> lists = Lists.newArrayList();
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
      int size = q.size();
      List<Integer> level = new LinkedList<>();
      for (int i = 0; i < size; i++) {
        TreeNode poll = q.poll();
        level.add(poll.val);
        //在一个层的树节点塞到queue中
        if (poll.l != null) {
          q.offer(poll.l);
        }
        if (poll.r != null) {
          q.offer(poll.r);
        }
      }
      lists.add(level);
    }
    return lists;
  }

  @Test
  public void test() {
    BSTCengXu cengxunTreeTest = new BSTCengXu();
    List<List<Integer>> leve = cengxunTreeTest.leve(root);
    System.out.println(leve);
  }

  List<Integer> cengxures = Lists.newArrayList();

  //层序遍历节点 用dfs前序遍历方法
  public void cengxu(TreeNode root, int dep) {
    if (root == null) return;
    if (cengxures.size() < dep) cengxures.add(root.val);
    cengxu(root.l, dep + 1);
    cengxu(root.r, dep + 1);
  }

  @Test
  public void test2(){
    cengxu(root,1);
  }

  List<Integer> list = Lists.newLinkedList();

  //前序遍历 递归
  public void pre(TreeNode root) {
    if (root == null) {
      return;
    }
    list.add(root.val);
    pre(root.l);
    pre(root.r);
  }

  @Test
  public void test3() {
    pre(this.root);
    System.out.println(list);
  }

  //前序遍历 迭代法
  public void preIt(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> vals = Lists.newLinkedList();

    stack.push(root);

    while (!stack.isEmpty()) {
      TreeNode pop = stack.pop();
      vals.add(pop.val);

      if (pop.r != null) stack.push(pop.r);
      if (pop.l != null) stack.push(pop.l);
    }
    System.out.println(vals);
  }

  @Test
  public void test4() {
    preIt(this.root);
  }

}
